题解 P1550 [USACO08OCT]打井Watering Hole

发表于 | 更新于

题意:$Farmer John $的农场缺水了。

他决定将水引入到他的 $n$ 个牧场。他准备通过挖若干井，并在各块田中修筑水道来连通各块田地以供水。在第 $i$ 号田中挖一口井需要花费 $W_i$ 元。连接 $i$ 号田与 $j$ 号田需要 $P_{i,j}$（$P_{j,i}=P_{i,j}$）元。

请求出 FJ 需要为使所有农场都与有水的农场相连或拥有水井所需要的最少钱数。

$1 \leqslant n \leqslant 300$，$1 \leqslant W_i \leqslant 10^5$，$1 \leqslant P_{i,j} \leqslant 10^5$。

做法最小生成树很容易发现，但是难点在于想单独打井，设一个源点$0$，把每个井与$0$连边，费用就是打井所需费用

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include <bits/stdc++.h>
using namespace std;
struct node{
    int u,v,d;
}a[3000000];
int cnt,x,n,m,ed,ans,f[400000];
bool cmp(node a,node b){
    return a.d<b.d;
}
int find(int k){
    return (f[k]==k)?k:(f[k]=find(f[k]));
}
void bing(int x,int y,int d){
    int u=find(x),v=find(y);
    if (u==v)return;
    f[u]=v;
    ans+=d;
    ++ed;
}
int main(){
    scanf("%d",&n);
    for (int i=1;i<=300000;i++)f[i]=i;
    for (int i=1;i<=n;i++){
        scanf("%d",&x);
        a[++cnt].v=i;a[cnt].d=x;
    }
    for (int i=1;i<=n;i++)
        for (int j=1;j<=n;j++){
            scanf("%d",&x);
            if (j<i)
                a[++cnt].u=j,a[cnt].v=i,a[cnt].d=x;
        }
    sort(a+1,a+1+cnt,cmp);
    for (int i=1;i<=cnt&&ed<=2*n+1;i++)
        bing(a[i].u,a[i].v,a[i].d);
    printf("%d",ans);
}